# -*- coding:utf-8 -*-
# 希尔排序

def shell_sort(list):
    n = len(list)
    step = n // 2
    while step > 0: # 最后的步长为1，此时就是一个标准的插入排序
        for cur in range(step, n):
            i = cur
            while i >= step and list[i-step] > list[i]:
                list[i - step], list[i] = list[i], list[i-step]
                i -= step
        step = step // 2
    return list


list = [54, 26, 93, 17, 77, 3, 31, 44, 55, 20]
print(shell_sort(list))